package org.aplombh.java.awcing.basic.struct.kmp;

public class KMP {
    private static final int N = 10010;
    private static final int M = 100010;

    int[] next = new int[N];

    public void kmp(int n, String p, int m, String s) {

        // next
        // 0 1 2 3 4 5 6
        // a b c a b c z
        // 0 0 0 1 2 3 0
        //                               next[0] = 0
        // i = 1, j = 0 | p[1] != p[0] | next[1] = 0 // j 尝试出门，不匹配，失败，回家。
        // i = 2, j = 0 | p[2] != p[0] | next[2] = 0 // j 再尝试出门，还是不行，回老家。
        // i = 3, j = 0 | p[3] == p[0] | next[3] = j++ = 1 // j 再尝试出门，发现了相同的！出门！并且做记录。
        // i = 4, j = 1 | p[4] == p[1] | next[4] = j++ = 2 // j 继续走，发现还是可以，记录
        // i = 5, j = 2 | p[5] == p[2] | next[5] = j++ = 3 // 状态不错，继续走
        // i = 6, j = 3 | p[6] != p[3] | j = next[2] = 0 | next[6] =0 // 碰壁了，尝试从2开始重新尝试，但是2最后退回老家，sad。
        //
        // i表示第几位，j代表距离，如果和当前i位置匹配，j继续走，如果不比配，j尽可能往回退，退无可退，就回到了快乐老家 (0)。


        // 求next数组
        // Figure out the next array
        for (int i = 1, j = 0; i < n; i++) {
            // 如果匹配失败，回退
            // If the match fails, roll back
            while (j != 0 && p.charAt(i) != p.charAt(j)) j = next[j - 1];
            // 如果匹配成功，记录位置
            // If the match is successful, the location is recorded
            if (p.charAt(i) == p.charAt(j)) j++;
            next[i] = j;
        }

        // 模式匹配
        for (int i = 0, j = 0; i < m; i++) {
            // 如果匹配失败，回退
            // If the match fails, roll back
            while (j != 0 && s.charAt(i) != p.charAt(j)) j = next[j - 1];
            // 当前位置匹配成功，继续往下匹配
            // Current location matched successfully, continue to match
            if (s.charAt(i) == p.charAt(j)) j++;
            // 模式串匹配成功，输出位置并继续往后匹配
            // The pattern string matches successfully, outputs the position and continues to match
            if (j == n) {
                System.out.println(i - n + 1);
                // 匹配成功，进行下一次匹配
                j = next[j - 1];
            }
        }
    }
}
